package com.lzq.leetcode.hoot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class s15 {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        for (int a = 0; a < len; a++) {
            if (a > 0 && nums[a] == nums[a-1]) {
                continue;
            }

            int b = a + 1;
            int c = len - 1;
            while (b < c) {
                int target = nums[a] + nums[b] + nums[c];
                if (target < 0) {
                    do {
                        ++b;
                    } while (b < c && nums[b] == nums[b-1]);
                } else if (target > 0) {
                    do {
                        --c;
                    } while (b < c && nums[c] == nums[c+1]);
                } else {
                    List<Integer> temp = Arrays.asList(nums[a], nums[b], nums[c]);
                    ans.add(temp);
                    do {
                        ++b;
                    } while (b < c && nums[b] == nums[b-1]);
                }
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        new s15().threeSum(new int[]{-1,0,1,2,-1,-4});
    }
}
